/**
 * @file   RBT.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:47:35 2020
 * 
 * @brief  a Red-Black Tree
 * 
 * 
 */

#include <iostream>

#define Black 1
#define Red 0

template <typename T>
class Binary_Tree {
protected:
    typedef int Color;
    class Node {
    public:
        T vmax; //the max value of the sub tree
	T high; //high value of the node
        T low; //high value of the node
	Node* lc;
	Node * rc;
	Node * parent;
	Color color;
    };
    int num; // the number of nodes
    Node * root;
    Node * ahead; //connect the root
    Node * min(Node * _x); //return the min node
    Node * tree_search(T _low, T _high); //return the first node that its value equals _x
    void inorder_walk(Node * _x) const; //print the sub tree
    void adjust_insert(Node * _x); //adjust the insert node
    void adjust_delete(Node * _x); //adjust the delete node
    void left_rotate(Node * _x);
    void right_rotate(Node * _x);
    void link(Node * u, Node * v); //replace u with v
    void draw(Node * _x) const; //draw the constructure of the tree
    void left_change_max(Node * _x);
    void right_change_max(Node * _x);
    void find_vmax(Node * _x); //find the new vmax
    Node * search(T _low, T _high) const;
public:
    Binary_Tree() {
	root = NULL;
	num = 1;
	ahead = new Node;
	ahead->color = Black;
    };
    Binary_Tree(T _low, T _high);
    void insert(T _low, T _high); //insert node
    void Delete(T _low, T _high); //delete node    
    void inorder_walk(); //print the tree
    void draw() const; //print the tree
    void clear(Node * _x); //delete the whole tree
    void result(T _low, T _high); //print the result
    ~Binary_Tree();
};

/**
 * @file   RBT.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Wed Dec 16 22:00:30 2020
 * 
 * @brief  find the interval overlap it
 * 
 * 
 */

template < typename T>
void Binary_Tree<T>::result(T _low, T _high) {
    Node * x = search(_low, _high);
    std::cout << "The interval overlap [" << _low << ", " << _high << "] is [" << x->low << ", " << x->high << "]" << std::endl;
}

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::search(T _low, T _high) const {
    Node * index = root;
    //if it's not the nil and we have not found the interval continue
    while (index->lc!=root && (index->low>_high || index->high<_low)) {
	//if left child's vmax > _low, go left
	if (index->lc->vmax>=_low) {
	    index = index->lc;
	} else {
	    index = index->rc;
	}
    }
	
    return index;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:38:14 2020
 * 
 * @brief  draw the whole tree
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::draw(Node * _x) const {
    int floor = 0; //the end pos
    int down = 1;  //the pos now
    int check = 0;
    while (Black) {
	check = 0; //check if we have printed something
	down = 1; //come back to the root
	floor++; //we need to print the next floor
	Node * index = _x;
	Node * last = _x;

	int n = num;
	int count = 0;
	while (n>1) {
	    n = n >> 1;
	    count++;
	}
	int height = 2*count;
	while (Black) {
	    //if we have not come back, go to left until tail / down==floor
	    while (index->lc->lc!=root && down<floor && index!=last->parent) {
		last = index;
		index = index->lc;
		down++;
	    }
	    if (down==floor) {
		//we arrive, then back		
	        for(int i=0;i<(height-floor)*(height-floor)/2;i++) {
		    std::cout << " ";
		}
		if (index->lc->lc==root) {
		    std::cout << "X";
		}
		if (index==index->parent->lc) {
		    std::cout << "/";
		}
		std::cout << "[" << index->low << ", " << index->high << "]";	
		if (index==index->parent->rc) {
		    std::cout << "\\";
		}
		if (index->rc->lc==root) {
		    std::cout << "X";
		}
		check = 1;
		last = index;
		if (index==root) {
		    break;
		}
		index = index->parent;		
		down--;
	    } else {
		//if we have not come back from right, go to right unless tail
		if (index->rc->lc!=root && index->rc!=last) {
		    last = index;
		    index = index->rc;
		    down++;
		} else {
		    //else back
		    last = index;
		    index = index->parent;
		    down--;
		    //we have no way, end the loop
		    if (index->lc==root) {
			break;
		    }
		}
	    }
	}
	std::cout << std::endl;
	//check if we have printed something, if not, break
	if (check==0) {
	    break;
	}
    }
}

template <typename T>
void Binary_Tree<T>::draw() const {
    std::cout << "The whole tree is:" << std::endl;
    draw(root);
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:33:46 2020
 * 
 * @brief  output the node 
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::inorder_walk() {
    inorder_walk(root);
    std::cout << std::endl;
}

template <typename T>
void Binary_Tree<T>::inorder_walk(Node * _x) const {
    if (_x->lc!=root) {
	//print the left
	inorder_walk(_x->lc);
	//print this node
	std::cout << "[[" << _x->low << ", " << _x->high << "], vmax=" << _x->vmax << ", color=" << _x->color << "]" << std::endl;
	//print the right
	inorder_walk(_x->rc);
    }
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:36:05 2020
 * 
 * @brief  find the node
 * 
 * 
 */

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::tree_search(T _low, T _high) {
    Node * index = root;
    Node * last = index;
    //this function is used by delete function, it will decrease the vmax
    while (index->lc!=root) {
	if (_low<index->low) {
	    last = index;
	    index = index->lc;
	} else if (_low==index->low && _high==index->high){
	    return index;
	} else {
	    last = index;
	    index = index->rc;
	}
    }
	
    return index;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:35:22 2020
 * 
 * @brief  find the min
 * 
 * 
 */

template <typename T>
typename Binary_Tree<T>::Node * Binary_Tree<T>::min(Node * _x) {
    Node * index = _x;
    Node * last = index;
    //return the most left node, it is the min
    while (index->lc->lc!=root) {
	index = index->lc;
    }
    //index don't have left child
    if (last->vmax==index->high) {
	last->vmax = last->high;
	if (last->vmax < last->rc->vmax) {
	    last->vmax = last->rc->vmax;
	}
	if (last->vmax < index->rc->vmax) {
	    last->vmax = index->rc->vmax;
	}
    }
    last = last->parent;
    while (last->lc!=root) {
	find_vmax(last);
	last = last->parent;
    }
    
    return index;
}

template <typename T>
void Binary_Tree<T>::find_vmax(Node * _x) {
    _x->vmax = _x->high;
    if (_x->vmax < _x->lc->vmax) {
	_x->vmax = _x->lc->vmax;
    }
    if (_x->vmax < _x->rc->vmax) {
	_x->vmax = _x->rc->vmax;
    }
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:37:53 2020
 * 
 * @brief  Rotate
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::right_rotate(Node * _x) {
    //if nothing left, return
    if (_x->lc->lc==root) {
	return;
    }
    Node * y = _x->lc;
    y->parent = _x->parent;
    //if _x==root, reset root
    if (_x==root) {
	root = y;
    } else {
	if (_x==_x->parent->lc) {
	    _x->parent->lc = y;
	} else {
	    _x->parent->rc = y;
	}
    }
    _x->lc = y->rc;
    y->rc->parent = _x;
    y->rc = _x;
    _x->parent = y;
}

template <typename T>
void Binary_Tree<T>::left_rotate(Node * _x) {
    //if nothing right, return
    if (_x->rc->lc==root) {
	return;
    }
    Node * y = _x->rc;
    y->parent = _x->parent;
    //if _x==root, reset root
    if (_x==root) {
	root = y;
    } else {
	if (_x==_x->parent->rc) {
	    _x->parent->rc = y;
	} else {
	    _x->parent->lc = y;
	}
    }
    _x->rc = y->lc;
    y->lc->parent = _x;
    y->lc = _x;
    _x->parent = y;
}

template <typename T>
void Binary_Tree<T>::left_change_max(Node * _x) {
    _x->rc->vmax = _x->vmax;
    _x->vmax = _x->high;    
    if (_x->vmax < _x->lc->vmax) {
	_x->vmax = _x->lc->vmax;
    }
    if (_x->vmax < _x->rc->lc->vmax) {
	_x->vmax = _x->rc->lc->vmax;
    }
}

template <typename T>
void Binary_Tree<T>::right_change_max(Node * _x) {
    _x->lc->vmax = _x->vmax;
    _x->vmax = _x->high;    
    if (_x->vmax < _x->rc->vmax) {
	_x->vmax = _x->rc->vmax;
    }
    if (_x->vmax < _x->lc->rc->vmax) {
	_x->vmax = _x->lc->rc->vmax;
    }
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:33:27 2020
 * 
 * @brief  delete one node
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::Delete(T _low, T _high) {
    //find the node
    Node * del_node = tree_search(_low, _high);
    //if not found, return
    if (del_node->lc==root) {
	return;
    }
    //record the pos
    Node * add_node = del_node;
    Node * adj_node = del_node;
    //record the origin color of add_node
    Color add_origin_color = add_node->color;
    //if only has one sub tree, just link it
    //record the adj_node as left/right node of del_node
    if (del_node->lc->lc==root) {
	adj_node = del_node->rc;
	link(del_node, adj_node);
    } else if (del_node->rc->lc==root) {
	adj_node = del_node->lc;
	link(del_node, adj_node);
    } else {
	//if two sub tree, find the successor add_node, record its color
	add_node = min(del_node->rc);
	adj_node = add_node->rc;
	add_origin_color = add_node->color;
	//if add_node is NOT its right node, connect their right node 
	if (add_node!=del_node->rc) {
	    link(add_node, adj_node);
	    add_node->rc = del_node->rc;	    
	}
	add_node->lc = del_node->lc;
	link(del_node, add_node);	
	add_node->lc->parent = add_node;
	add_node->rc->parent = add_node;
	//set the new node's color the same as del_node
	add_node->color = del_node->color;
    }
    //if origin color is red, nothing happen, else need to adjust
    //adjust the vmax of add_node
    Node * index = add_node;
    while (index->lc!=root) {
	find_vmax(index);
	index = index->parent;
    }
    if (add_origin_color==Black) {
	adjust_delete(adj_node);
    }
    delete del_node;
}

template <typename T>
void Binary_Tree<T>::adjust_delete(Node * _x) {
    //if me is red, change it to black, else loop
    //if me is root, the same
    Node * me = _x;
    while (me!=root && me->color==Black) {
	//me is the left child
	if (me==me->parent->lc) {
	    Node * brother = me->parent->rc;
	    //if brother is red, change it to black
	    if (brother->color==Red) {
		me->parent->color = Red;
		brother->color = Black;
		left_change_max(me->parent);
		left_rotate(me->parent);
		brother = me->parent->rc;
	    }
	    //if brother's two children are black, let brother become red, move me to the parent
	    if (brother->lc->color==Black && brother->rc->color==Black) {
		brother->color = Red;
		me = me->parent;
	    } else {
		//if brother's right is black, change the node, make left black
		if (brother->rc->color==Black) {
		    brother->lc->color = Black;
		    brother->color = Red;
		    right_change_max(brother);
		    right_rotate(brother);
		    brother = brother->parent;
		}
		brother->color = me->parent->color;
		me->parent->color = Black;
		brother->rc->color = Black;
		left_change_max(me->parent);
		left_rotate(me->parent);
		me = root;
	    }
	} else {
	    //the same as the left condition
	    Node * brother = me->parent->lc;
	    if (brother->color==Red) {
		me->parent->color = Red;
		brother->color = Black;
		right_change_max(me->parent);
		right_rotate(me->parent);
		brother = me->parent->lc;
	    }
	    if (brother->rc->color==Black && brother->lc->color==Black) {
		brother->color = Red;
		me = me->parent;
	    } else {
		if (brother->lc->color==Black) {
		    brother->rc->color = Black;
		    brother->color = Red;
		    left_change_max(brother);
		    left_rotate(brother);
		    brother = brother->parent;
		}
		brother->color = me->parent->color;
		me->parent->color = Black;
		brother->lc->color = Black;
		right_change_max(me->parent);
		right_rotate(me->parent);
		me = root;
	    }
	}
    }    
    me->color = Black;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:39:48 2020
 * 
 * @brief  replace
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::link(Node * _u, Node * _v) {
    //in this function, _v will take the place of _u
    if (_u==root) {
	root = _v;
    } else if (_u==_u->parent->lc) {
	_u->parent->lc = _v;
    } else {
	_u->parent->rc = _v;
    }
    _v->parent = _u->parent;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:32:59 2020
 * 
 * @brief  insertion
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::insert(T _low, T _high) {
    //insert the node to the NULL node
    Node * index = root;
    Node * add = new Node;
    num++;
    add->low = _low;
    add->high = _high;
    add->color = Red;
    add->vmax = _high;
    Node * tail = new Node;
    tail->color = Black;
    tail->lc = root;
    tail->vmax = 0;
    
    if (root==NULL) {
	Node * tail_l = new Node;
	add->lc = tail;
	add->rc = tail_l;
	tail_l->color = Black;
	tail->lc = tail->parent = add;
	tail_l->lc = tail_l->parent = add;
	tail_l->vmax = 0;
	add->parent = ahead;
	ahead->lc = ahead->rc = add;
        root = add;	
    } else {
        while (Black) {
	    if (index->vmax < _high) {
		index->vmax = _high;
	    }
	    if (_low<index->low) {
		if (index->lc->lc==root) {
		    index->lc->parent = add;
		    add->lc = index->lc;
		    add->rc = tail;
		    tail->parent = add;
		    add->parent = index;
		    index->lc = add;
		    break;		    
		} else {
		    index = index->lc;
		}
	    } else {
		if (index->rc->lc!=root) {
		    index = index->rc;
		} else {
		    index->rc->parent = add;
		    tail->parent = add;
		    add->lc = tail;
		    add->rc = index->rc;
		    add->parent = index;
		    index->rc = add;
		    break;
		}
	    }
	}	
    }
    adjust_insert(add);
}

template <typename T>
void Binary_Tree<T>::adjust_insert(Node * _x) {
    Node * me = _x;
    Node * father = me->parent;    
    //when parent is Red, loop
    while (father->color==Red) {
	if (father->parent->lc==father) {
	    Node * uncle = father->parent->rc;
	    //case 1:parent and uncle are red
	    if (uncle->color==Red) {
	        father->color = Black;
		uncle->color = Black;
		me = father->parent;
		father = me->parent;
		me->color = Red;
	    } else {
		//case 2:uncle is black
		if (father->lc!=me) {
		    left_change_max(father);
		    left_rotate(father);
		    me = me->lc;
		    father = me->parent;
		}
		father->color = Black;
		father->parent->color = Red;
		right_change_max(father->parent);
		right_rotate(father->parent);
	    }
	} else {
	    Node * uncle = father->parent->lc;
	    //case 1:parent and uncle are red
	    if (uncle->color==Red) {
	        father->color = Black;
		uncle->color = Black;
		me = father->parent;
		father = me->parent;
		me->color = Red;
	    } else {
		//case 2:uncle is black
		if (father->rc!=me) {
		    right_change_max(father);
		    right_rotate(father);
		    me = me->rc;
		    father = me->parent;
		}
		father->color = Black;
		father->parent->color = Red;
		left_change_max(father->parent);
		left_rotate(father->parent);
	    }
	}
    }
    root->color = Black;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:32:26 2020
 * 
 * @brief  create the tree
 * 
 * 
 */

template <typename T>
Binary_Tree<T>::Binary_Tree(T _low, T _high) {
    root = new Node;
    Node * tail_r = new Node;
    Node * tail_l = new Node;
    ahead = new Node;
    num = 1;
    
    root->low = _low;
    root->high = _high;
    root->lc = tail_l;
    root->rc = tail_r;
    root->parent = ahead;
    root->vmax = _high;
    
    ahead->lc = ahead->rc = root;
    ahead->color = Black;
    root->color = Black;

    tail_r->lc = tail_r->parent = root;
    tail_l->lc = tail_l->parent = root;
    tail_r->color = tail_l->color = Black;
    tail_r->vmax = tail_l->vmax = 0;
}

/**
 * @file   Binary_Tree.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sun Dec  6 18:32:39 2020
 * 
 * @brief  delete the tree
 * 
 * 
 */

template <typename T>
void Binary_Tree<T>::clear(Node * _x) {
    if (_x!=NULL && _x!=root) {
        clear(_x->lc);
	Node * tmp = _x->rc;
	delete _x;
        clear(tmp);
    }
}

template <typename T>
Binary_Tree<T>::~Binary_Tree() {
    delete ahead;
    clear(root);
}
